package dtst;

public class MySingleList {
    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
        public ListNode head;

        //头插法
        public void addFirst(int data) {
            ListNode newNode = new ListNode(data);
            if (head == null) {
                head = newNode;
                return;
            }
            newNode.next = head;
            head = newNode;

        }

        //尾插法
        public void addLast(int data) {
            ListNode listNode = new ListNode(data);
            if (head == null) {
                head = listNode;
                return;
            }
            ListNode curNode = head;
            while (curNode.next != null) {
                curNode = curNode.next;
            }
            curNode.next = listNode;
        }

        //任意位置插入,第一个数据节点为0号下标
        public void addIndex(int index, int data) {
            if (index<0||index>size()) {
                System.out.println("插入失败,输入下标不合法");
                return;
            }
            if (index==0) {
                addFirst(data);
                return;
            }
            if (index==size()) {
                addLast(data);
                return;
            }
            ListNode newNode=new ListNode(data);
            ListNode curNode=head;
            int count=0;
            while (count!=index-1) {
                curNode=curNode.next;
            }
            newNode.next=curNode.next;
            curNode.next=newNode;
            return;
        }

        //查找是否包含关键字key是否在单链表当中
        public boolean contains(int key) {
            if (head==null) {
                return false;
            }
            ListNode curNode=head;
            while (curNode!=null) {
                if (curNode.val==key) {
                    return true;
                }
                curNode=curNode.next;
            }
            return false;
        }


        private ListNode findKeyPrevNode(int key) {
            ListNode CurNode = this.head;
            while (CurNode != null) {
                if (CurNode.next.val == key) {
                    return CurNode;
                }
                CurNode = CurNode.next;
            }
            return null;
        }

        //删除第一次出现关键字为key的节点
        public void remove(int key) {
            if (head==null) {
                System.out.println("没有要删除的节点");
                return;
            }
            if (head.val==key) {
                head=head.next;
            }
            ListNode curNode=head;
            while (curNode.next!=null) {
                if (curNode.next.val==key) {
                    curNode.next=curNode.next.next;
                    return;
                }
                curNode=curNode.next;
            }
            System.out.println("没有要删除的数字");
        }

        //删除所有值为key的节点
        public void removeAllKey(int key) {
            ListNode cur=head.next;
            ListNode prev=head;
            while (cur!=null) {
                if (cur.val==key) {
                  prev.next=cur.next;
                  cur=cur.next;

                }else {
                    prev=cur;
                    cur=cur.next;
                }
            }
            if (head.val==key) {
                head=head.next;
            }

        }

        //得到单链表的长度
        public int size() {
            if (head == null) {
                return 0;
            }
            int count = 0;
            ListNode curNode = head;
            while (curNode != null) {
                count++;
                curNode = curNode.next;
            }
                return count;

        }
            public void clear () {
                head=null;
            }
            public void display () {
                ListNode cur=head;
                while (cur!=null) {
                    System.out.print(cur.val+" ");
                    cur=cur.next;
                }

        }

}


